1. Technical Field
The invention relates to efficient utilization of physical memory by virtual storage systems and more particularly to efficient storage of segments from application written for segmentation type virtual storage systems in a multitasking data processing system utilizing demand paging type virtual storage. Still more particularly, the invention relates to efficient utilization of physical memory in a virtual storage system for a multitasking operating system providing shared objects between processes.
2. Description of the Related Art
The term "virtual storage" is normally associated with a computer system that has the capability of addressing a memory space much larger than that available in the system's physical memory. Virtual storage is not a new concept. In fact, virtual storage capability first appeared in the Atlas computer system constructed at the University of Manchester in England in 1960. Today almost all general-purpose computers support virtual storage, with the possible exception of some real-time systems.
The key to the virtual storage concept is the disassociation of memory addresses referenced by a process from those used in the physical memory of a computer system. The addresses referenced by a process are called virtual addresses. The addresses used by the physical memory are called physical addresses. The range of virtual addresses to which a process may reference is called a virtual address space or process domain. Since the virtual address space, as seen by a process, is much larger than the limited amount of physical memory installed in the system, the virtual address space is divided into smaller blocks. Each of these blocks, when in use by a running process, will correspond to a certain block (of the same size) in physical memory. Since the amount of physical memory is limited, the blocks that are not in use will be kept on disk, out of memory. As the process executes, it will need to reference different blocks, and these blocks will be brought into memory dynamically. To make room for new blocks to be brought into the limited physical memory, some blocks that are no longer in use by the running process might be swapped out to disk. Thus the operating system must keep track of where in physical memory the various virtual storage blocks have been placed.
From a performance standpoint, there is some question as to whether the blocks should all be the same size, or of different sizes. When the blocks are the same size, they are called pages, and the associated virtual memory organization is called paging. When the blocks may be of different sizes, they are called segments, and the associated virtual memory organization is called segmentation. The Intel 80286 microprocessors support a segmentation type of virtual storage organization. Segmentation involves moving the entire segments in and out of memory. Each segment can be as small as one byte or can span over several Kbytes of physical memory (up to 64 Kbytes on the Intel 80286). Unused or infrequently used segments can be moved, swapped out to disk, or simply discarded if they have not been modified, to make room for new segments to be brought into memory. However, a segment cannot be fragmented; it must occupy one contiguous piece of physical memory. These features prevent the allocation of a segment larger than the physical memory, and make it very difficult to manipulate large segments. The task of finding or creating a large enough contiguous piece of physical memory to load a segment becomes increasingly difficult as the segment sizes grow much beyond the 64-KB limit imposed by the Intel 80286 architecture and operating systems manufactured by International Business Machines Corporation OS/2 Version 1.X. These problems, coupled with the fact that multiple segments must be simultaneously present in physical memory to begin the execution of a program, present insurmountable challenges to a segment-based virtual memory architecture. In addition, many non-Intel processors use a flat, non-segmented memory model preferred by many application developers.
Paging involves moving fixed-size chunks (pages) of code and data in and out of memory. To make room for newly referenced pages that are not present in memory, unused or infrequently used pages in memory can be swapped out to disk, or simply discarded (if they have not been modified). However, unlike segmentation, there is no need to move pages among frames in physical memory since all pages are of the same size and need not be contiguous in physical memory.
The architecture of the Intel 80386 and 80486 processors can support both paging and segmentation. The key feature of these processors is the support for 32-bit wide segments in a paging-based virtual memory environment. While segmentation is a feature that is not commonly found in other families of processors, such as the Motorola 68000 or RISC processors, the 32-bit wide segments can be used to simulate a flat, 32-bit wide virtual address space, which is a very common feature of other processors. On the Intel 80286, the segmentation hardware maps a selector and an offset through the appropriate descriptor table entry to a physical address. On the Intel 80386 and 80486, processors with paging enabled, another level of indirection exists between the selector mapping and physical memory: the linear address space. The linear space is a 32-bit wide flat or virtual address space which is mapped through the page tables to physical memory. If a selector is created to map the entire 4 Gbytes of the linear address space as code and another is created to map the same linear space as data, and if these selectors are loaded into an application's segment registers and are never changed, then, for all practical purposes, an application can view the underlying memory management as not having a segmented address space, but as having a flat address space.
An application may allocate regions within the flat, 32-bit linear address space. Such an allocated region is called an object. Conceptually, an object is like a segment in that it may be treated as a discrete entity for the purposes of certain operations. However, unlike segments, all objects addressable by a process in a paging environment can be referenced directly without the need to load any segment register with a special value. On the Intel 80386 processors, the use of paging not only permits the allocation of objects larger than the 64-KB limit, but also larger than the available physical memory. Paging also allows more efficient swapping and memory overcommit algorithms as the pages are fixed in size (4 Kbytes). Paging also eliminates all the pitfalls of the swap-file fragmentation problems present in segmentation systems.
An arena is a contiguous subset of the linear address space. There are three types of arenas: private, shared, and system. A private arena is analogous to the set of private selectors, and the shared arena is analogous to the set of shared selectors in the segmented memory model. The private and shared selectors are mapped through the Local Descriptor Table (LDT). The system arena is the portion of the linear address space used by the operating system itself. This is similar to the memory space mapped by the set of selectors in the Global Descriptor Table (GDT) in the segmented memory model used by the Intel 80286 processors.
The simplest and most obvious way to partition the flat, 32-bit linear address space into private and shared areas (arenas) is to put objects with private addresses at one end and objects with shared addresses at the other, and let them grow toward each other, much as one would manage two stacks at the same time. In the 32-bit wide OS/2, the private arena begins at the low end of the user's flat address space and the shared arena will start at the high end. The private and shared arenas will grow toward each other, but they may never overlap. The boundary between them depends on the requirements of the applications running on the system, but there are minimum and maximum values between which the boundary will be constrained to remain.
As its name implies, the private arena of a process is unique to that process, that is, each process has its own private arena to map its private code and data objects. However, the same cannot be said for the shared arena. The shared arena is shared across all processes running in the system. When a process references a Dynamically Linked Library (DLL), the DLL's code and data objects will be loaded into the shared arena. If a 16-bit wide DLL is referenced by a 16-bit wide process, the descriptors for the DLL would be allocated from the top end of the LDT of the process to map to its linear address space. Since the DLL can be shared by other processes in the system, the same descriptors would have to be allocated and reserved in the LDTs of all other processes. When one of these processes actually references the DLL, these reserved descriptors in that process' LDT would be initialized to map to the same DLL code and data segments. In other words, when a 16-bit wide DLL is loaded into memory, the same descriptor slots (selectors) will be allocated in the LDTs of all 16-bit wide processes running in the system. The next DLL loaded will be mapped by a different set of descriptors in all LDTs in the system. In short, each initialized descriptor in the shared arena will map to the same locations in the virtual memory (selector), linear memory (flat), and physical memory, regardless of which LDT the descriptor belongs to. LDT descriptors in the private arena are allocated from the bottom (low address) up, while descriptors for DLLs in the shared arena are allocated from the top (high address) down. Furthermore, LDT descriptors for each DLL to be loaded is also allocated from the higher addresses down.
As mentioned previously, the 32-bit wide OS/2 Version 2.0 will support both 16-bit and 32-bit applications. This means that the system must be able to understand both the selector:offset (16:16) addressing format used in 16-bit applications and the linear (0:32) addressing format used in 32-bit applications within the same process. There must be a simple method to translate a 0:32 address into a 16:16 address, and vice versa. Such an address translation process is referred to as address thunking.
In OS/2 1.X versions, the maximum amount of memory a process can own is limited by the amount of memory its LDT can map. On the Intel processors, an LDT can have 8192 descriptors, each mapping up to 64 Kbytes of memory. Therefore, the maximum amount of memory an application can own is 512 Mbytes. This amount excludes the system-owned memory mapped by the GDT, but it does include all shared memory allocated by all processes running in the system. In the 32-bit wide OS/2 Version 2.0, this limit has been retained for each process in order to have a one-to-one mapping between the 16:16 and 0:32 addressing formats. In other words, each descriptor in the LDT will map to a corresponding 64-Kbyte piece of the linear (flat) address space. This unique mapping between the LDT and the linear address space is called tiling. The first 512 Mbytes of the linear address space where tiling takes place is referred to as the Compatibility Region (CR).
With tiling, the conversion from 16:16 to 0:32 addressing formats, and vice versa, is performed by a short sequence of shift and add operations. For 16-bit applications, the base address of every segment will be equal to the 13 high-order bits of the selector (the index of the corresponding descriptor in the LDT) multiplied by 64 Kbytes. The low 3 bits in a selector indicate the table and ring protection levels, and therefore are not representative of distinct memory addresses. Thus, the conversion from a 16:16 (selector:offset) address to a 0:32 (linear, flat) address can be done via this formula: EQU linaddr=(selector&gt;&gt;3)&lt;&lt;16+offset
By using the inverse of the algorithm above, we can construct a valid 16:16 address for any byte within a tiled object as follows: EQU offset=linaddr & 0xFFFF EQU selector=((linaddr&gt;&gt;16)&lt;&lt;3).vertline.4.vertline.CPL
Despite its advantages in thunking (address conversions between the 16:16 and 0:32 formats), tiling is not the perfect solution. New applications that wish to use existing 16:16 code must be careful of the tiling boundaries within objects. In particular, a single logical entity, such as a buffer or a name string, must no cross a 64-Kbyte boundary if it is to be used by 16:16 code since the entity would not be completely accessible using a single selector. Language tools must provide support to insure that these mistakes are not made.
Efficient utilization of limited physical memory is served by sharing of data objects and code objects between different processes on a multitasking operating system. A virtual storage system should provide constraints on the organization of the virtual storage for each process that will permit sharing of frames in physical memory between processes.